package 电话号码的字母组合;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * createTime: 2025/4/12 22:24
 * description:
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * @author AirMan
 */
public class Solution {
    public List<String> letterCombinations(String digits) {
        // 回溯
        // 回溯的参数：digits，startIndex(标记搜索到哪一个数字)
        // 回溯的返回值：void
        // 回溯的终止条件：纵向遍历结束，搜索到树的叶子节点 =》 path.size() == digits.length
        // 单层回溯搜索的逻辑：横向搜索的宽度就是 digits 的长度，digits的长度就代表了一个组合中包含的
        // 字符数量，纵向搜索就是digits的每一个数字中挑选一个字符组合成一条“路径”
        // “还有一个纵向搜索” =》 从数字中搜索
        if (digits.isEmpty()){
            return Collections.emptyList();
        }
        backtracking(digits, 0);
        return result;
    }
    char[][] chararter = new char[][]{
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'}
    };
    List<String> result = new ArrayList<>();
    List<Character> path = new ArrayList<>();
    public void backtracking(String digits, int startIndex){
        if (path.size() == digits.length()){
            result.add(path.stream().map(String::valueOf).collect(Collectors.joining()));
            return;
        }
        // 左闭右开
        for (int i = startIndex; i < digits.length(); i++){
            for (int j = 0; j < 4; j++){
                // 处理节点
                int number = digits.charAt(startIndex) - '0';
                // 不是数字7，9就只有三个字符
                if (j == 3 && number != 7 && number != 9){
                    continue;
                }
                char c = chararter[number - 2][j];
                path.add(c);
                // 回溯搜索
                backtracking(digits, i + 1);
                // 回溯，撤回节点
                path.remove(path.size() - 1);
            }
        }
    }
}
